#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

//int mySqrt(int x) {
//    for (long long i = 1; i <= x; i++)
//    {
//        if (i * i == x)
//            return i;
//        else if (i * i > x)
//            return i - 1;
//    }
//    return 0;
//}

int mySqrt(int x) {
    if (x == 0)
        return 0;
    int left = 1;
    int right = x;
    while (left < right)
    {
        long long mid = left + (right - left + 1) / 2;
        if (mid * mid <= x)
            left = mid;
        else
            right = mid - 1;
    }
    return left;
}
#include<vector>
int peakIndexInMountainArray(vector<int>& arr)
{
    int left = 0;
    int right = arr.size() - 1;

    while (left < right)
    {
        int mid = left + (right - left + 1) / 2;
        if (arr[mid] > arr[mid - 1])
            left = mid;
        else
            right = mid - 1;
    }
    return left;
}

int takeAttendance(vector<int>& records)
{
    int left = 0;
    int right = records.size() - 1;
    while (left < right)
    {
        int mid = left + (right - left) / 2;

        if (records[mid] == mid)
            left = mid + 1;
        else
            right = mid;
    }

    if (records[left] == left)
        return left + 1;
    return left;
}

class Solution
{
    int left, right, n;
    string path;
    vector<string> ret;
public:
    vector<string> generateParenthesis(int _n)
    {
        n = _n;
        dfs();
        return ret;
    }

    void dfs()
    {
        if (right == n)
        {
            ret.push_back(path);
            return;
        }

        if (left < n)
        {
            path.push_back('(');
            left++;
            dfs();

            path.pop_back();
            left--;
        }

        if (right < left)
        {
            path.push_back(')');
            right++;
            dfs();

            path.pop_back();
            right--;
        }
    }
};